package com.coder.algorithm.offer_2;

import java.util.Arrays;
import java.util.Locale;

/**
 * 替换空格
 *
 * @author yuhushuan
 * @date 2020/5/28 01:24
 */
public class _05_1_ReplaceSpaces {
    public static void main(String[] args) {
        int[] A1;
        int[] A2;

        // A2 中的数字都小于 A1 中的数字；
        // A2 中的数字都大于 A1 中的数字；
        // A2 中的数字交叉于 A1 中的数字；

        System.out.println("A2 中的数字都小于 A1 中的数字；");
        A1 = new int[]{5, 6, 7, 8, 9, 0, 0, 0, 0};
        A2 = new int[]{1, 2, 3, 4};
        print(A1, 5, A2, A2.length);

        System.out.println("A2 中的数字都大于 A1 中的数字；");
        A1 = new int[]{1, 2, 3, 4, 0, 0, 0, 0, 0};
        A2 = new int[]{5, 6, 7, 8, 9};
        print(A1, 4, A2, A2.length);

        System.out.println("A2 中的数字交叉于 A1 中的数字；");
        A1 = new int[]{1, 3, 5, 7, 9, 0, 0, 0, 0};
        A2 = new int[]{2, 4, 6, 8};
        print(A1, 5, A2, A2.length);

        System.out.println("A2 中的数字交叉于 A1 中的数字，且存在重复数字；");
        A1 = new int[]{1, 3, 6, 8, 9, 0, 0, 0, 0};
        A2 = new int[]{2, 4, 6, 8};
        print(A1, 5, A2, A2.length);

        // A1 为 null；A2 为 null
        System.out.println("A1 为 null；A2 为 null");
        print(null, 0, null, 0);

        // A1 为 null；A2 为 []
        System.out.println("A1 为 null；A2 为 []");
        print(null, 0, new int[0], 0);

    }

    private static void print(int[] target, int tLength, int[] src, int sLength) {
        System.out.println(String.format(Locale.getDefault(), "被插入排序数组：%s\n待插入排序数组：%s\n插入后排序数组：%s",
                Arrays.toString(target), Arrays.toString(src),
                Arrays.toString(insert(target, tLength, src, sLength))));
        System.out.println();
    }

    /**
     * 有两个排序的数组 A1 和 A2，内存在 A1 的末尾有足够的空余空间容纳 A2。
     * 请实现一个函数，把 A2 中的所有数字插入 A1 中，并且所有的数字是排序的。
     *
     * @return
     */
    private static int[] insert(int[] target, int tLength, int[] src, int sLength) {
        if (target == null) {
            return null;
        }
        if (src == null) {
            return target;
        }
        int tPos = tLength + sLength - 1;
        int tp = tLength - 1;
        int sp = sLength - 1;
        while (sp >= 0 && tPos >= 0) {
            if (tp >= 0 && target[tp] >= src[sp]) {
                target[tPos] = target[tp];
                tPos--;
                tp--;
            } else {
                target[tPos] = src[sp];
                tPos--;
                sp--;
            }
        }
        return target;
    }
}


